package xiaohong.data.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PostfixExpressionDemo {


    public static void main(String[] args) {

        // 50 * 50 + 90 - 100 + 60 / 30   =>  50 50 * 90 + 100 - 60 30 / +
        // 25 * 10 - 250 + 100 / 50 + 80 - 2 - 40 * 2
        // 25 10 * 250 - 100 50 / + 80 + 2 - 40 2 * -
        String express = "50 * 50 + 90 - 100 + 60 / 30";
        String express1 = "25 * 10 - 250 + 100 / 50 - 2 + 80";
        String express2 = "100 + 70 * 50 / 10 - 25 * 15";         // 100 70 50 10 / * + 25 15 * -   450 - 375 = 75
        String express3 = "(100 + 70) * (50 / 10) - (25 * 15)";   // 100 70 + 50 10 / * 25 15 * -   170 * 5 - 850 - 375 = 475

        String expr = "50 50 * 90 + 100 - 60 30 / +";
        String expr1 = "25 10 * 250 - 100 50 / + 80 + 2 - 40 2 * -";
        System.out.println(expr);
        System.out.println(expr1);

        List<String> exprList = splitExpression(express);

        Stack<String> stack = new Stack<>();
        List<String> postfixExpression = new ArrayList<>();



        for (String item : exprList) {
            if (item.matches("\\d+")){
                postfixExpression.add(item);
                continue;
            }else {
                if (stack.isEmpty() || stack.peek().equals("(")){
                    stack.push(item);
                    continue;
                }else if(isPriority(item)){ // 如果是运算符
                    if (stack.isEmpty()){
                        stack.push(item);
                        continue;
                    }
                    while (!stack.isEmpty() && hasLowerOrEqualPriority(stack.peek() , item)){
                        // 将栈顶的运算符弹出并压入s2
                        String pop = stack.pop();
                        postfixExpression.add(pop);
                    }
                    stack.push(item);
                    continue;
                }else if (item.equals("(")){    // 如果是 左括号 (
                    stack.push(item);
                    continue;
                }else if (item.equals(")")){    // 如果是 右括号 )
                    while (!stack.isEmpty()){
                        String pop = stack.pop();
                        if (pop.equals("(")){
                            continue;
                        }
                        postfixExpression.add(pop);
                    }
                }else {
                    throw new RuntimeException("表达式匹配出错");
                }
            }
        }

        while (!stack.isEmpty()){
            String pop = stack.pop();
            postfixExpression.add(pop);
        }

        System.out.println("exprList = " + exprList);
        System.out.println(postfixExpression);

        Stack<Integer> stackInt = new Stack<>();
        postfixExpression.forEach(item -> {
            if (item.matches("\\d+")) {
                stackInt.push(Integer.parseInt(item));
            }else {
                int num;
                switch (item) {
                    case "*" -> {
                        Integer num2 = stackInt.pop();
                        Integer num1 = stackInt.pop();
                        num = num1 * num2;
                    }
                    case "+" -> {
                        Integer num2 = stackInt.pop();
                        Integer num1 = stackInt.pop();
                        num = num1 + num2;
                    }
                    case "-" -> {
                        Integer num2 = stackInt.pop();
                        Integer num1 = stackInt.pop();
                        num = num1 - num2;
                    }
                    case "/" -> {
                        Integer num2 = stackInt.pop();
                        Integer num1 = stackInt.pop();
                        num = num1 / num2;
                    }
                    default -> throw new ArithmeticException("符号不正确");
                }
                stackInt.push(num);
            }
        });
        System.out.println("表达式的结果=" + stackInt.pop());

    }


    public static boolean isPriority(String op1) {
        return op1.equals("*") || op1.equals("-") || op1.equals("+") || op1.equals("/");
    }

    public static boolean hasLowerOrEqualPriority(String op1, String op2) {
        int priority1 = getOperatorPriority(op1);
        int priority2 = getOperatorPriority(op2);
        return priority1 >= priority2;
    }

    public static int getOperatorPriority(String operator) {
        if ("*".equals(operator) || "/".equals(operator)) {
            return 2;
        } else if ("+".equals(operator) || "-".equals(operator)) {
            return 1;
        }
        return 0; // 左括号的优先级设为0，这里只是为了统一比较逻辑，实际左括号有特殊处理逻辑
    }


    public static List<String> splitExpression(String expression) {
        List<String> list = new ArrayList<>();
        int i = 0;
        while (i < expression.length()) {
            char c = expression.charAt(i);
            if (Character.isDigit(c)) {
                StringBuilder numBuilder = new StringBuilder();
                while (i < expression.length() && (Character.isDigit(c) || c == '.')) {
                    numBuilder.append(c);
                    i++;
                    if (i < expression.length()) {
                        c = expression.charAt(i);
                    }
                }
                list.add(numBuilder.toString());
            } else {
                if (' '!= c) {  // 添加这行判断，当字符不是空格时才添加到列表
                    list.add(String.valueOf(c));
                }
                i++;
            }
        }
        return list;
    }



}
